|
Muller's method is a root-finding algorithm, a numerical method for solving equations of the form ''f''(''x'') = 0. It was first presented by David E. Muller in 1956. Muller's method is based on the secant method, which constructs at every iteration a line through two points on the graph of ''f''. Instead, Muller's method uses three points, constructs the parabola through these three points, and takes the intersection of the ''x''-axis with the parabola to be the next approximation. ==Recurrence relation== Muller's method is a recursive method which generates an approximation of the root ξ of ''f'' at each iteration. Starting with the three initial values ''x''0, ''x''-1 and ''x''-2, the first iteration calculates the first approximation ''x''1, the second iteration calculates the second approximation ''x''2, the third iteration calculates the third approximation ''x''3, etc. Hence the ''k''''th'' iteration generates approximation ''x''''k''. Each iteration takes as input the last three generated approximations and the value of ''f'' at these approximations. Hence the ''k''''th'' iteration takes as input the values ''x''''k''-1, ''x''''k''-2 and ''x''''k''-3 and the function values ''f''(''x''''k''-1), ''f''(''x''''k''-2) and ''f''(''x''''k''-3). The approximation ''x''''k'' is calculated as follows. A parabola ''y''''k''(''x'') is constructed which goes through the three points (''x''''k''-1, ''f''(''x''''k''-1)), (''x''''k''-2, ''f''(''x''''k''-2)) and (''x''''k''-3, ''f''(''x''''k''-3)). When written in the Newton form, ''y''''k''(''x'') is : where ''f''(''x''''k''-2 ) and ''f''(''x''''k''-2, ''x''''k''-3 ) denote divided differences. This can be rewritten as : where : The next iterate ''x''''k'' is now given as the solution closest to ''x''''k''-1 of the quadratic equation ''y''''k''(''x'') = 0. This yields the recurrence relation : In this formula, the sign should be chosen such that the denominator is as large as possible in magnitude. We do not use the standard formula for solving quadratic equations because that may lead to loss of significance. Note that ''x''''k'' can be complex, even if the previous iterates were all real. This is in contrast with other root-finding algorithms like the secant method, Sidi's generalized secant method or Newton's method, whose iterates will remain real if one starts with real numbers. Having complex iterates can be an advantage (if one is looking for complex roots) or a disadvantage (if it is known that all roots are real), depending on the problem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Muller's method」の詳細全文を読む スポンサード リンク
|